{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第六章 栈、队列和双端队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1 栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈（stack）：一系列对象组成的collection，对象的插入和删除操作遵循后进先出（LIFO）的原则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在栈中插入、删除、访问的对象只能是栈顶。（自动售卖机）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈的例子：历史网址，在后退时按照的顺序就是后进先出，网址用栈来存储；撤销功能，将每一步操作存储在栈中，撤销时也是按照后进先出的顺序。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6.1.1 栈的抽象数据类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈是一种支持以下两种操作的抽象数据类型（ADT）：\n",
    "\n",
    "1. 将一个元素添加到栈顶。（push）\n",
    "2. 移除并返回栈顶的元素。如果栈为空，该操作报错或出错。（pop）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "除操作方法外还有访问方法：\n",
    "\n",
    "1. 返回栈顶元素但不移除，栈为空将报错。（top）\n",
    "2. 返回栈是否为空。（is_empty）\n",
    "3. 返回栈中元素的个数。（len）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6.1.2 简单的基于数组的栈实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然数组或者list可以实现栈的功能，但是同时也包含了许多栈不能实现的功能，不能与栈混为一谈。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "适配器模式（The Adapter Pattern）：适配器设计模式用于将一个类改编为另一个类，两个类可能在有些功能上相同，但需要不同的命名或者接口，可以通过建立一个新类，新类中用一个旧类的实例来初始化以及实现类的方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过适配器模式用Python的list类来构造一个stack类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过list类构造stack类（底层是一个array），在stack类中，只允许特定操作和访问的存在，不允许其他非法操作，这能够起到一些限制作用，可能也是使用stack而不是array来存储一些元素的优点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于list而言，pop和top（假设已经在stack类中实现）在list为空时会触发IndexError，由于stack没有index，所以需要重新定义一个新的异常类。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class ArrayStack:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._data == []\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._data.append(e)\n",
    "    \n",
    "    def top(self):\n",
    "        if self._data:\n",
    "            return self._data[-1]\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def pop(self):\n",
    "        if self._data:\n",
    "            return self._data.pop()\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "3\n",
      "1\n",
      "False\n",
      "3\n",
      "True\n"
     ]
    },
    {
     "ename": "Empty",
     "evalue": "Stack is empty!",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mEmpty\u001b[0m                                     Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-2-db4831535e3f>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      8\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmystack\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmystack\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_empty\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 10\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmystack\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-1-e0f54fb62316>\u001b[0m in \u001b[0;36mpop\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m     26\u001b[0m             \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_data\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     27\u001b[0m         \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 28\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mEmpty\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'Stack is empty!'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mEmpty\u001b[0m: Stack is empty!"
     ]
    }
   ],
   "source": [
    "mystack = ArrayStack()\n",
    "mystack.push(3)\n",
    "mystack.push(4)\n",
    "print(mystack.pop())\n",
    "print(mystack.top())\n",
    "print(len(mystack))\n",
    "print(mystack.is_empty())\n",
    "print(mystack.pop())\n",
    "print(mystack.is_empty())\n",
    "print(mystack.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "栈的所有操作和访问都是常量时间，上面实现的ArrayStack的pop和push操作要进行摊销分析。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6.1.3 使用栈实现数据的逆置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以文件为例，逆序打印每一行："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_file(filename):\n",
    "    S = ArrayStack()\n",
    "    original = open(filename)\n",
    "    for line in original:\n",
    "        S.push(line.rstrip('\\n'))\n",
    "    original.close()\n",
    "    \n",
    "    output = open(filename, 'w')\n",
    "    while not S.is_empty():\n",
    "        output.write(S.pop() + '\\n')\n",
    "    output.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个序列按照一个顺序压入栈中，再依次弹出将得到反序的序列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6.1.4 括号和HTML标记匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在算术表达式中，括号要成对出现，即不能多出一边括号，同时，一对括号中的括号也要成对出现，不能一个括号在一对括号中，另一个在这对括号之外。要判断算术表达式是否正确，可以使用栈，在遇到左括号时压入栈，然后遇到右括号时与栈顶的括号进行判断，如果栈为空，报错；如果不匹配，报错；遍历完算术表达式的每个字符后，如果过程中未报错，且栈为空，则算术表达式正确。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_matched(expr):\n",
    "    lefty = '({['\n",
    "    righty = ')}]'\n",
    "    S = ArrayStack()\n",
    "    for c in expr:\n",
    "        if c in lefty:\n",
    "            S.push(c)\n",
    "        elif c in righty:\n",
    "            if S.is_empty():\n",
    "                return False\n",
    "            if righty.index(c) != lefty.index(S.pop()):\n",
    "                return False\n",
    "    return S.is_empty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "若算术表达式长度为n，则上述算法时间复杂度为O(n)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "类似的思想，可以用于HTML等标记语言中检查标签是否成对出现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_matched_html(raw):\n",
    "    S = ArrayStack()\n",
    "    j = raw.find('<')\n",
    "    while j != -1:\n",
    "        k = raw.find('>', j+1)\n",
    "        if k == -1:\n",
    "            return False\n",
    "        tag = raw[(j+1):k]\n",
    "        if not tag.startswith('/'):\n",
    "            S.push(tag)\n",
    "        else:\n",
    "            if S.is_empty():\n",
    "                return False\n",
    "            if tag[1:] != S.pop():\n",
    "                return False\n",
    "        j = raw.find('<', k+1)\n",
    "    return S.is_empty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列（queues）：一系列对象组成的collection，对象的插入和删除操作遵循先入先出（FIFO）的原则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "插入元素只能插入到队尾，删除元素只能删除队首的元素。（通常将允许插入元素的一端称为队尾，允许删除元素的一端称为队首）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "跟排队有关的都可以用队列存储，如打印机、网址请求等等。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列的抽象数据类型（ADT）是一系列对象的collection，定义的基本操作是：\n",
    "\n",
    "1. Q.enqueue(e)：向队列Q的队尾添加一个元素（入队）。\n",
    "2. Q.dequeue(e)：向队列Q中移除并返回第一个元素（离队），队列为空则触发错误。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还定义了一些访问方法：\n",
    "\n",
    "1. Q.first()：返回队列的第一个元素但不移除，如果队列为空则触发错误。\n",
    "2. Q.is_empty()：队列是否为空。\n",
    "3. len(Q)：返回队列Q中元素的数量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 6.2.2 基于数组的队列实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将Python的list类作为适配器类，编写queues类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于数组移除第一个元素效率很低，所以不能很简单地跟栈一样改编，而要进行更大程度上优化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以不将队列的元素原封不动的复制到list，而是用一个index来表示list中属于队列元素的部分，但是这样可能导致一边出队一边入队很多次后，list的长度远远长于queues。也就是所有曾经入队过的元素都会在list中，那么长时间积累下来将十分耗费内存。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一种比较好的解决办法是，创建一个长度为N的数组，使队首从接近list末尾的地方开始，让队列的元素从list末尾向list开头延伸，在入队操作时，只需将list开头部分后的元素更新，离队时只需更新索引，假设队首开始的索引是f，那么更新索引的办法是(f+1)%N，这样f=N-1时，能将索引更新到0，在不断离队和入队的操作过程中，队列的队首和队尾在list中的位置是循环移动的，在这个过程中只需要保证queues的总长度不超过N即可。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "队列的代码实现如下（基于循环lsit）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class ArrayQueue:\n",
    "    \n",
    "    DEFAULT_CAPACITY = 10\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY\n",
    "        self._size = 0\n",
    "        self._front = 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty')\n",
    "        return self._data[self._front]\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Queue is empty')\n",
    "        answer = self._data[self._front]\n",
    "        self._data[self._front] = None\n",
    "        self._front = (self._front + 1) % len(self._data)\n",
    "        self._size -= 1\n",
    "        return answer\n",
    "    \n",
    "    def enqueue(self):\n",
    "        if self._size == len(self._data):\n",
    "            self._resize(2 * len(self.data))\n",
    "        avail = (self._font + self._size) % len(self._data)\n",
    "        self._data[avail] = e\n",
    "        self._size += 1\n",
    "    \n",
    "    def resize(self, cap):\n",
    "        old = self._data\n",
    "        self._data = [None] * cap\n",
    "        walk = self._front\n",
    "        for k in range(self.size):\n",
    "            self._data[k] = old[walk]\n",
    "            walk = (1 + walk) % len(old)\n",
    "        self._front = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这种实现方式下，底层数组的长度虽然不必为进入过队列的元素个数，但是由于没有数组的缩减操作，将导致数组的长度与出现过的最长的队列长度相近，仍然会造成浪费。因此新增一个策略，当队列的长度降到数组长度的1/4时，缩减数组为原来的1/2。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于数组的队列实现的各种操作的时间复杂度均为O(1)，由于增加和减少元素涉及动态数组，因此会涉及到摊销分析的方法。从这里大体可以看出queues与array的差别了，如果是array直接来实现离队的操作，需要O(n)，而以数组为基础，使用循环数组实现的queues，却能达到O(1)的时间复杂度，这也是为什么在特定的情境下要用特定的数据结构，因为速度快，花费的时间少。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.3 双端队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双端队列（double-ended queue、deque）：支持在队列的头部和尾部都进行插入和删除操作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双端队列的抽象数据类型（ADT，从更具体的层面定义了双端队列的操作）：\n",
    "\n",
    "1. add_first(e): 向双端队列的前面添加一个元素e。\n",
    "2. add_last(e): 在双端队列的后面添加一个元素e。\n",
    "3. delete_first(): 从双端队列中移除并返回第一个元素。若双端队列为空，则触发错误。\n",
    "4. delete_last(): 从双端队列中移除并返回最后一个元素。若双端队列为空，则触发错误。\n",
    "\n",
    "还有一些访问操作：\n",
    "\n",
    "1. first(): 返回（但不移除）双端队列的第一个元素。若双端队列为空，则触发错误。\n",
    "2. last(): 返回（但不移除）双端队列的最后一个元素。若双端队列为空，则触发错误。\n",
    "3. is_empty(): 是否为空。\n",
    "4. len(): 返回双端队列中元素的个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双端队列的数组实现方法：与队列一样。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "colllections模块实现了双端队列，并且定义了一些新的方法，如访问第j个，清除所有内容等，这些在抽象数据类型中没有定义，但是加上也无伤大雅。只要保证添加和删除元素只能在首尾即可。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.4 练习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "R-6.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class ArrayStack:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._data == []\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._data.append(e)\n",
    "    \n",
    "    def top(self):\n",
    "        if self._data:\n",
    "            return self._data[-1]\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def pop(self):\n",
    "        if self._data:\n",
    "            return self._data.pop()\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self._data)\n",
    "     \n",
    "def transfer(S, T):\n",
    "    for i in range(len(S)):\n",
    "        T.push(S.pop())\n",
    "    return T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "S = ArrayStack()\n",
    "T = ArrayStack()\n",
    "\n",
    "for i in range(10):\n",
    "    S.push(i)\n",
    "\n",
    "print(S)\n",
    "transfer(S, T)\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "R-6.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class ArrayStack:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._data == []\n",
    "    \n",
    "    def push(self, e):\n",
    "        self._data.append(e)\n",
    "    \n",
    "    def top(self):\n",
    "        if self._data:\n",
    "            return self._data[-1]\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def pop(self):\n",
    "        if self._data:\n",
    "            return self._data.pop()\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def remove_all(self):\n",
    "        if len(self._data) == 1:\n",
    "            return self.pop()\n",
    "        else:\n",
    "            self.pop()\n",
    "            self.remove_all()\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self._data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "S = ArrayStack()\n",
    "for i in range(10):\n",
    "    S.push(i)\n",
    "\n",
    "print(S)\n",
    "S.remove_all()\n",
    "print(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "R-6.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "def myreverse(mylist):\n",
    "    mystack = ArrayStack()\n",
    "    for i in range(len(mylist)):\n",
    "        mystack.push(mylist.pop(0))\n",
    "    for i in range(len(mystack)):\n",
    "        mylist.append(mystack.pop())\n",
    "    return mylist\n",
    "    \n",
    "mylist = [k for k in range(10)]\n",
    "print(myreverse(mylist))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "R-6.10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为底层数组的长度要比队列长，因此从索引0开始循环取队列的数，可能导致队列中的数无法完全迁移，中间会出现一些None值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "R-6.11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "class MyQueue:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._queue = collections.deque()\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self._queue)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self) == 0\n",
    "    \n",
    "    def enqueue(self, value):\n",
    "        self._queue.append(value)\n",
    "    \n",
    "    def dequeue(self):\n",
    "        return self._queue.pop()\n",
    "    \n",
    "    def first(self):\n",
    "        return self._queue[1]\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self._queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([])\n",
      "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
      "1\n",
      "deque([])\n"
     ]
    }
   ],
   "source": [
    "myqueue = MyQueue()\n",
    "\n",
    "print(myqueue)\n",
    "\n",
    "for i in range(10):\n",
    "    myqueue.enqueue(i)\n",
    "\n",
    "print(myqueue)\n",
    "print(myqueue.first())\n",
    "\n",
    "for i in range(10):\n",
    "    myqueue.dequeue()\n",
    "\n",
    "print(myqueue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-6.16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "class full(Exception):\n",
    "    pass\n",
    "\n",
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class ArrayStack:\n",
    "    \n",
    "    def __init__(self, maxlen):\n",
    "        self._data = []\n",
    "        self._maxlen = maxlen\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._data == []\n",
    "    \n",
    "    def push(self, e):\n",
    "        if len(self) == self._maxlen:\n",
    "            raise full('Stack is too long!')\n",
    "        else:\n",
    "            self._data.append(e)\n",
    "        \n",
    "    def top(self):\n",
    "        if self._data:\n",
    "            return self._data[-1]\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def pop(self):\n",
    "        if self._data:\n",
    "            return self._data.pop()\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def remove_all(self):\n",
    "        if len(self._data) == 1:\n",
    "            return self.pop()\n",
    "        else:\n",
    "            self.pop()\n",
    "            self.remove_all()\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self._data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "ename": "full",
     "evalue": "Stack is too long!",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mfull\u001b[0m                                      Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-47-2f4309c8bed9>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m11\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m     \u001b[0mmystack\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpush\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-46-1421417bf577>\u001b[0m in \u001b[0;36mpush\u001b[1;34m(self, e)\u001b[0m\n\u001b[0;32m     19\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mpush\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     20\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_maxlen\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 21\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mfull\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'Stack is too long!'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     22\u001b[0m         \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     23\u001b[0m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_data\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0me\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mfull\u001b[0m: Stack is too long!"
     ]
    }
   ],
   "source": [
    "mystack = ArrayStack(10)\n",
    "\n",
    "for i in range(11):\n",
    "    mystack.push(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-6.17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "class full(Exception):\n",
    "    pass\n",
    "\n",
    "class Empty(Exception):\n",
    "    pass\n",
    "\n",
    "class ArrayStack:\n",
    "    \n",
    "    def __init__(self, maxlen):\n",
    "        self._data = [None] * maxlen\n",
    "        self._first = 0\n",
    "        self._last = 0\n",
    "        self._maxlen = maxlen\n",
    "    \n",
    "    def __len__(self):\n",
    "        return (self._last - self._first)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self) == 0\n",
    "    \n",
    "    def push(self, value):\n",
    "        if len(self) == self._maxlen:\n",
    "            raise full('Stack is too long!')\n",
    "        else:\n",
    "            self._data[self._last] = value\n",
    "            self._last += 1\n",
    "        \n",
    "    def top(self):\n",
    "        if not self.is_empty():\n",
    "            return self._data[-1]\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def pop(self):\n",
    "        if not self.is_empty():\n",
    "            value = self._data[self._last - 1]\n",
    "            self._data[self._last - 1] = None\n",
    "            self._last -= 1\n",
    "            return value\n",
    "        else:\n",
    "            raise Empty('Stack is empty!')\n",
    "    \n",
    "    def remove_all(self):\n",
    "        if len(self) == 1:\n",
    "            return self.pop()\n",
    "        else:\n",
    "            self.pop()\n",
    "            self.remove_all()\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self._data[self._first:self._last])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "mystack = ArrayStack(10)\n",
    "\n",
    "for i in range(10):\n",
    "    mystack.push(i)\n",
    "    \n",
    "print(mystack)\n",
    "\n",
    "for i in range(10):\n",
    "    mystack.pop()\n",
    "\n",
    "print(mystack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-6.20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "stack对range(n)中n个数实施n次push操作，在中间穿插pop操作，可以输出不同的排列顺序，这是基本思想。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C-6.26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "两个栈实现队列，每次队列的enqueue操作，都将value也push到第一个栈中，每次deque操作，都将第一个栈中所有的value都弹出，压入到第二个栈中，然后进行一次pop，然后从第二个栈中弹出所有元素并压入第一个栈中。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
